/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 * --------------------------------------------
 * @implemented by Edwin Wong and Seyed Amir Mirsalimi
 * @date 5/29/2012
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

int P_SIZE = PageFile::PAGE_SIZE;
/*
 * BTreeIndex constructor
 * treeHeight is defined to be 0 at root
 */
BTreeIndex::BTreeIndex()
    :rootPid(-1), treeHeight(0),depth(0),cPid(1)
{
}

/*
 * Open the index file in read or write mode.
 * Assume the page corresponding to pageid 0 of any file is reserved
 * to save tree information.
 * First 4 bytes is the rootPid, next 4 bytes is tree height.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    
    char t_buff[P_SIZE];
    //check for failure to open
    RC t_rc;
    t_rc = pf.open(indexname, mode);
    if(t_rc!=0) return t_rc;     
    
	//read info page if open correctly
    
	int last_page = pf.endPid();

	//if the file was empty or just created
	//we preset the root to 1 and the height to 0 if the mode was 'w'
	//if in reading mode we return an error since the file was not 
	//formated corectlly
	
	if(last_page == 0){
		if( (mode == 'w') || (mode == 'W')){
			int root = 1;
			memcpy(t_buff, &root,sizeof(PageId));
			memcpy(t_buff+sizeof(PageId), &treeHeight, sizeof(int));
			t_rc=pf.write(0, t_buff);
			return 0;
		}else{
			return RC_FILE_READ_FAILED;
		}
	}
	
    t_rc=pf.read(0, t_buff); //read info page & check for bugs
	if(t_rc!=0)
		return t_rc;
    

	//pageid 0 would store useful tree information such as
	//tree height, number of nodes
	memcpy(&rootPid, t_buff, sizeof(PageId));
	cPid = rootPid;
	memcpy(&treeHeight, t_buff+sizeof(PageId), sizeof(int));
    
     
    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	setHeightRoot(treeHeight,rootPid);
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * Recursive implementation of insert
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
	//bottom case: we are at a leaf node
	RC rc;
	PageId pid = cPid;
	PageId new_pid;
	int new_key;
	char t_buff[P_SIZE];
	if(depth == getTreeHeight()){
		
		BTLeafNode leaf;
		
		//empty file
		if(rootPid <= 0){
			rootPid = pid;
			leaf.initialize();	
			leaf.setNextNodePtr(0);
		}
		if((rc = leaf.read(cPid, pf)) < 0)
			return rc;
		if((rc = leaf.insert(key,rid)) >=0){
			cPid = getRootPid();
			depth = 0;
			leaf.write(pid, pf);
			return 0;
		}
		
		if(rc != RC_NODE_FULL){
			cPid = getRootPid();
			depth = 0;
			return rc;
		}
		
		///at this point there must be an overflow in the leafnode
		///so we do a split and insert
		BTLeafNode nleaf;
		nleaf.initialize();
		nPid = pf.endPid();
		nleaf.setNextNodePtr(nPid);
		
		if((rc =leaf.insertAndSplit(key, rid, nleaf, nKey)) < 0){
			cPid = getRootPid();
			depth = 0;
			return rc;
		}
			
		leaf.write(pid, pf);
		nleaf.write(nPid, pf);
		
		if(getTreeHeight() == 0){
			new_pid = pf.endPid();
			BTNonLeafNode nRoot;
			nRoot.initializeRoot(pid,nKey,nPid);
			nRoot.write(new_pid,pf);
			treeHeight++;
			rootPid = new_pid;
			cPid = getRootPid();
			depth = 0;
			return 0;
		}
		
		
		depth--;
		return RC_NODE_FULL;
	}
	
	BTNonLeafNode node;
	if((rc = node.read(cPid, pf)) < 0){
		cPid = getRootPid();
		depth = 0;
		return rc;
	}
	//PageId child;
	if((rc = node.locateChildPtr(key,cPid)) < 0){
		cPid = getRootPid();
		depth = 0;
		return rc;
	}
	
	
	///recursive call
	depth++;
	rc = insert(key,rid);

	if(rc >= 0){
		cPid = getRootPid();
		depth = 0;
		return 0;
	}
	else if(rc != RC_NODE_FULL){
		cPid = getRootPid();
		depth = 0;
		return rc;
	}
	
	if((rc = node.insert(nKey,nPid)) >=0){
		cPid = getRootPid();
		depth = 0;
		node.write(pid,pf);
		return 0;
	}
			
	if(rc != RC_NODE_FULL){
		cPid = getRootPid();
		depth = 0;
		return rc;
	}
			
	//at this point we have an overflow in the nonleaf nodes
	BTNonLeafNode nonleaf;
	new_pid = pf.endPid();
	
	nonleaf.setKeyCount(0);
	nonleaf.updatePidKey();

	if((rc = node.insertAndSplit(nKey, nPid, nonleaf, new_key)) < 0){
		cPid = getRootPid();
		depth = 0;
		return rc;
	}

	node.write(pid,pf);
	nonleaf.write(new_pid,pf);
	
	nKey = new_key;
	nPid = new_pid;
	
	if(depth == 0){
		new_pid = pf.endPid();
		BTNonLeafNode nRoot;
		nRoot.initializeRoot(pid,nKey,nPid);
		nRoot.write(new_pid,pf);
		treeHeight++;
		rootPid = new_pid;
		cPid = getRootPid();
		depth = 0;
		return 0;
	}
	
	return RC_NODE_FULL;

 
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    int t_eid;

	//case: uninitialized tree
    if(rootPid==-1)
    {
        //retrieve junk values in cusror
        cursor.pid=-1;
        cursor.eid=-1;
        return RC_END_OF_TREE;
    }
    if(treeHeight==0) //case: only root node
    {
        BTLeafNode root;
        RC t_rc;
        //read from root
        t_rc = root.read(rootPid,pf);
        if(t_rc!=0)
            return t_rc;
        //locate key in root and return eid position
        t_rc = root.locate(searchKey, t_eid); 
        if(t_rc!=0)
            return t_rc;
        //key is found
        cursor.pid=rootPid;
        cursor.eid=t_eid;
        return 0;
    }
    else //case: treeheight >0
    {
        BTNonLeafNode nroot;//root in this case is a nonleaf node
        BTLeafNode nleaf;
        int level_pos=0;//start at root level
        int cur_pid=rootPid;//start at rootPid; contains current pid
        RC temp_rc;


        //deal with searching nonleaf nodes
        //when loop breaks, we'll get the pntr to leaf node
        while(level_pos < treeHeight)
        {
            //read current node & check for errors
            temp_rc=nroot.read(cur_pid,pf);
            if(temp_rc!=0) return temp_rc;

            //find the child ptr in the current node
            //should always return a pointer as long as there's a node 
            //with valid keys
            temp_rc= nroot.locateChildPtr(searchKey,cur_pid);
            if(temp_rc!=0) return temp_rc;
            level_pos++;
        }
        //now deal with searching leaf node
        //read & check
        temp_rc=nleaf.read(cur_pid, pf);
        if(temp_rc!=0) return temp_rc;
        //locate leaf node & check;
        temp_rc = nleaf.locate(searchKey, t_eid); 
        if(temp_rc!=0) return temp_rc;

        //ref values
        cursor.pid = cur_pid;
        cursor.eid = t_eid;
    }
    
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    BTLeafNode t_leaf;
    RC t_rc;
    PageId n_pid;
    if(cursor.pid<0 || cursor.eid<0) return RC_INVALID_CURSOR;
    //read node
    t_rc=t_leaf.read(cursor.pid, pf);
    if(t_rc!=0) return t_rc;

    //get key and rid
    t_rc=t_leaf.readEntry(cursor.eid, key, rid);
    if(t_rc!=0) return t_rc;

    //check boundaries
    if(cursor.eid < t_leaf.getKeyCount()-1)
    {
        cursor.eid++;
        return 0;
    }
    printf("\nend of node\n");
    //reached the end, look for next node
    n_pid = t_leaf.getNextNodePtr();
    //check for invalid pid
    if(n_pid<=0)
    {
        return RC_INVALID_PID;
    }
    else
        cursor.pid=n_pid;
    cursor.eid=0; //restart to 0

    return 0;

}


/*
 * Set the rootPid and treeHeight information at the
 * info node (pid=0) to height and rPid
 */
void BTreeIndex::setHeightRoot(int height, PageId rPid)
{
    char buffer[P_SIZE];
    memcpy(buffer, &rPid, sizeof(PageId));
    memcpy(buffer+sizeof(PageId), &height, 4);
    pf.write(0,buffer);
}
